package basic.study.leetcode;

/**
 * @ClassName Mid79
 * @Description 单词搜索
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/24 15:17
 * @Version 1.0
 */
public class Mid79 {
    class Solution {
        boolean exist = false;

        public boolean exist(char[][] board, String word) {
            if (board == null || board.length == 0 || board[0].length == 0) {
                return exist;
            }

            int index = 0;//匹配到word的哪个index了
            boolean[][] visited = new boolean[board.length][board[0].length];
            for (int row = 0; row < board.length; row++) {
                for (int col = 0; col < board[0].length; col++) {
                    if (board[row][col] == word.charAt(0)) {
                        recall(board, word, 0, visited, row, col);
                    }
                }
            }

            return exist;
        }

        private void recall(char[][] board, String word, int index, boolean[][] visited, int row, int col) {
            if (exist) {
                return;
            }

            //访问标记
            visited[row][col] = true;

            if (index == word.length()-1) {
                exist = true;
                return;
            }
            //左
            if (row - 1 >= 0 && visited[row-1][col] == false && board[row-1][col] == word.charAt(index+1)) {
                recall(board, word, index+1, visited, row-1, col);
            }
            //右
            if (row + 1 < board.length && visited[row+1][col] == false && board[row+1][col] == word.charAt(index+1)) {
                recall(board, word, index+1, visited, row+1, col);
            }
            //上
            if (col - 1 >= 0 && visited[row][col-1] == false && board[row][col-1] == word.charAt(index+1)) {
                recall(board, word, index+1, visited, row, col-1);
            }
            //下
            if (col + 1 < board[0].length && visited[row][col+1] == false && board[row][col+1] == word.charAt(index+1)) {
                recall(board, word, index+1, visited, row, col+1);
            }

            //回溯
            visited[row][col] = false;
        }
    }
}
